Exercici 8 (Tasca 5).
(R (decidable/recursive languages),
RE (semi-decidable/ recursively enumerable languages),
computable functions)
Characteritzacions de \mathbf{R} i \mathbf{RE}
Sigui S un llenguatge infinit.
- S\in \mathbf{RE} si i només si existeix una funció computable, total i injectiva f tal que \mathrm{Im}(f)=S.
- S\in \mathbf{R} si i només si existeix una funció computable, total i injectiva f que és monòtona creixent i tal que \mathrm{Im}(f)=S.
- S\in \mathbf{R} si i només si la funció característica de S, \chi_S, és computable.
Nota
Recordeu que, donada una funció f, \mathrm{Im}(f) és la imatge de f, és a dir, \mathrm{Im}(f)=\{y \mid \exists x\ y=f(x)\}. La funció característica d’un conjunt S és la funció booleana \chi_S tal que \chi_S(x)=1 si i només si x\in S.